package LeetCode.leetcode131;

import java.util.ArrayList;
import java.util.List;

public class Review1 {
    public List<List<String>> partition(String s) {
        List<List<String>> ans = new ArrayList<>();
        List<String> path = new ArrayList<>();
        backTracking(s, ans, 0, path);
        return ans;
    }
    public void backTracking(String s, List<List<String>> res, int index, List<String> path) {
        if (index == s.length()) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = index; i < s.length(); i++) {
            String subString = s.substring(index, i+1);
            if (checkValidString(subString)) {
                path.add(subString);
                backTracking(s,res,i+1,path);
                path.remove(path.size()-1);
            }
        }
    }
    public boolean checkValidString(String s) {
        if (s == null || s.isEmpty() || s.length() == 1) {
            return true;
        }
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) return false;
            left++;
            right--;
        }
        return  true;
    }
}
